/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2019年01月01日
*   描    述：
*   Copyright (C) 2019 All rights reserved.
*   
================================================================*/


#include <iostream>
#include <stack>
#include <vector>
using namespace std;

 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if( !root )
            return res;

        stack<TreeNode *>st;
        TreeNode *p = root;

        while( p || !st.empty() ){
            while( p ){
                res.push_back(p->val);
                st.push(p);
                p = p->left;
            }

            p = st.top();
            st.pop();
            p = p->right;
        }

        return res;
    }
};

